Developer CD Series 1994 November: Tool Chest/Dev.CD Nov 94.toast/Tool Chest/Development Tools & Languages/Dylan Related/Mindy-1.1 (sources only)/mindy-1.1/libraries/coll-ext/solist.dylan

Text File | 1994-06-29 | 5.3 KB | 146 lines | [TEXT/ttxt]

module:     solist
rcs-header:    $Header: solist.dylan,v 1.1 94/06/28 23:06:56 wlott Exp $
author:     Robert Stockton ([e-mail])
synopsis:    Provides "self-organizing lists".  These explicit key
        collections provide roughly the semantics of hash tables, but
        use a probabilistic implementation which provides O(n) worst
        case performance but can provide very fast constant time
        access in the best case.

//======================================================================
//
// Copyright (c) 1994  Carnegie Mellon University
// All rights reserved.
//
// Use and copying of this software and preparation of derivative
// works based on this software are permitted, including commercial
// use, provided that the following conditions are observed:
//
// 1. This copyright notice must be retained in full on any copies
//    and on appropriate parts of any derivative works.
// 2. Documentation (paper or online) accompanying any system that
//    incorporates this software, or any part of it, must acknowledge
//    the contribution of the Gwydion Project at Carnegie Mellon
//    University.
//
// This software is made available "as is".  Neither the authors nor
// Carnegie Mellon University make any warranty about the software,
// its performance, or its conformity to any specification.
//
// Bug reports, questions, comments, and suggestions should be sent by
// E-mail to the Internet address "[e-mail]".
//
//======================================================================

//======================================================================
// The "Self Organizing List" is a "poor man's hash table".  More precisely,
// <so-list> is a subclass of <mutable-explicit-key-collection> for which
// addition and retrieval are both linear in the worst case, but which use a
// probabilistic strategy which yields nearly constant time in the best case.
//
// Because they have a very low overhead, self-organizing lists may provide
// better peformance than hash tables in cases where references have a high
// degree of temporal locality.  They may also be useful in situations where
// it is difficult to create a proper hash function.
//
// Define new so-lists with
//
//   make(<so-list>, test: test)
//
// Test is expected to be an equality function.  In particular, it is expected
// to satisfy the identity and transitivity requirements described in chapter
// 5.  If not specified, test defaults to \==.
//======================================================================

define class <so-list> (<stretchy-collection>,
            <mutable-explicit-key-collection>)
  slot data :: <list>, init-value: #();
  // slot accessor provides method for standard collection op "key-test"
  slot key-test :: <function>, init-value: \==, init-keyword: test:;
end class;

define constant sol-fip-next-state =
  method (list :: <so-list>, state :: <list>) => (result :: <list>);
    tail(state);
  end method;

define constant sol-fip-finished-state? =
  method (list :: <so-list>, state :: <list>, limit)
    state == #();
  end method;

define constant sol-fip-current-key =
  method (list :: <so-list>, state :: <list>) => (result :: <object>);
    head(head(state));
  end method;


define constant sol-fip-current-element =
  method (list :: <so-list>, state :: <list>) => (result :: <object>);
    tail(head(state));
  end method;

define constant sol-fip-current-element-setter =
  method (value :: <object>,
      list :: <so-list>, state :: <list>) => (result :: <object>);
    tail(head(state)) := value;
  end method;

define constant sol-fip-copy-state =
  method (list :: <so-list>, state :: <list>) => (result :: <list>);
    state;
  end method;

define method forward-iteration-protocol (table :: <so-list>)
  values(table.data, #f, sol-fip-next-state, sol-fip-finished-state?,
     sol-fip-current-key, sol-fip-current-element,
     sol-fip-current-element-setter, sol-fip-copy-state);
end method forward-iteration-protocol;

define constant sol-no-default = pair(#f, #f);

define method element(table :: <so-list>, key :: <object>,
              #key default: default = sol-no-default)
  let list :: <list> = table.data;
  let test :: <function> = table.key-test;

  block (return)
    let first = head(list);    // depend upon head(#()) being defined
    case
      list == #() =>
    #f;    // fall through
      test(head(first), key) =>
    return(tail(first));
      otherwise =>
    for (prev = list then state,
         state = tail(list) then tail(state),
         until state == #())
      let elem = head(state);
      if (test(head(elem), key))
        tail(prev) := tail(state);
        tail(state) := list;
        table.data := state;
        return(tail(elem));
      end if;
    end for;
    end case;
    // We never reach this point if the element is present.
    if (default == sol-no-default) error("Key %= not in %=", key, table)
    else default
    end if;
  end block;
end method element;

define constant sol-no-value = pair(#f, #f);

define method element-setter(value, table :: <so-list>, key :: <object>)
  // Bring the existing element (if any) to the front of the list
  if (element(table, key, default: sol-no-value) == sol-no-value)
    // It wasn't there, so add it
    table.data := pair(pair(key, value), table.data);
  else
    // It was there, so change the value of the first element.
    tail(head(table.data)) := value;
  end if;
end method element-setter;